package greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by JiaJia on 2019/5/27 0027.
 */
public class PartitionLabels {
    public static List<Integer> partitionLabels(String s){
        int[] lastIndexOfChar=new int[26];
        for (int i = 0; i <s.length() ; i++) {
            lastIndexOfChar[char2Index(s.charAt(i))]=i;
        }
        List<Integer> partiions=new ArrayList<>();
        int firstIndex=0;
        while (firstIndex<s.length()){
            int lastIndex=firstIndex;
            for (int i = firstIndex; i <s.length()&&i<=lastIndex ; i++) {
                int index=lastIndexOfChar[char2Index(s.charAt(i))];
                if (index>lastIndex){
                    lastIndex=index;
                }
            }
            partiions.add(lastIndex-firstIndex+1);
            firstIndex=lastIndex+1;
        }
        return partiions;
    }
    private static int char2Index(char c){
        return c-'a';
    }

    public static void main(String[] args) {
        String s="ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s));
    }
}